package com.explorati.interview.interview.chapterfifteen;

public class SelectionSort {

	public static void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				// 如果第i个数大于后面的数就将第i个数和后面比他小的数互换，首先排出最小的数
				if (arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
	}

	public static void selectionSort1(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			//找出[i, j)区间中的最小值
			int min = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = { 4, 3, 52, 12, 53, 56, 78 };
		selectionSort(arr);
		for (int i : arr) {
			System.out.print(i + "\t");
		}

		System.out.println("");
		int[] arr1 = { 4, 3, 52, 12, 53, 56, 78 };
		selectionSort1(arr1);
		for (int i : arr1) {
			System.out.print(i + "\t");
		}

		System.out.println();
		int[] arr2 = SortArrayHelper.generateRandomArray(100, 0, 100);
		selectionSort(arr2);
		for (int i : arr2) {
			System.out.print(i + "\t");
		}
	}
}
